package pers.sloera.leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.stream.Collectors;

/**
 * 替换子串得到平衡字符串
 *
 * @author sloera
 * @date 2023-02-13 21:54:35
 */
class ReplaceTheSubstringForBalancedString {
    public static void main(String[] args) {
        Solution solution = new ReplaceTheSubstringForBalancedString().new Solution();
        System.out.println(solution.balancedString("WQWRQQQW"));
        System.out.println(solution.balancedString("QWER"));
        System.out.println(solution.balancedString("QQWE"));
        System.out.println(solution.balancedString("QQQW"));
        System.out.println(solution.balancedString("QQQQ"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int balancedString(String s) {
            int min = s.length();
            HashMap<String, Boolean> balancedCache = new HashMap<>();
            // int left = 0;
            // int right = 0;
            // while (left<s.length() && right <= s.length()) {
            //     String leftString = s.substring(0, left) + s.substring(right);
            //     //
            //     if (right - left > min) {
            //         break;
            //     }
            //     if (!isBalanced(leftString, right - left, balancedCache)) {
            //         right++;
            //     } else {
            //         min = Math.min(min, right - left);
            //         // 找到最短的匹配，后面的肯定都比这长
            //         break;
            //     }
            // }
            for (int leftIndex = 0; leftIndex < s.length() - 1; leftIndex++) {
                int rightIndex = leftIndex;
                while (true) {
                    // 越界 及 无匹配的必要
                    if (rightIndex > s.length() || rightIndex - leftIndex > min) {
                        break;
                    }
                    String leftString = s.substring(0, leftIndex) + s.substring(rightIndex);
                    if (!isBalanced(leftString, rightIndex - leftIndex, balancedCache)) {
                        rightIndex++;
                    } else {
                        min = Math.min(min, rightIndex - leftIndex);
                        // 找到最短的匹配，后面的肯定都比这长
                        break;
                    }
                }
            }
            return min;
        }

        private boolean isBalanced(String leftString, int redundant, HashMap<String, Boolean> balancedCache) {
            return balancedCache.computeIfAbsent(leftString, key -> {
                int redundantTmp = redundant;
                // 按字符分组
                Map<Integer, Long> groupMap = key.chars().boxed().collect(Collectors.groupingBy(x -> x, Collectors.counting()));
                // 要平衡，则最终数量一致，剩余的字符串是不可变的，所以对齐最大值
                int max = groupMap.values().stream().mapToInt(Long::intValue).max().orElse(0);
                if (max == 0) {
                    return true;
                }
                for (Character character : Arrays.asList('Q', 'W', 'E', 'R')) {
                    // 替换的子串是否能够满足balance的基础条件
                    redundantTmp -= max - Optional.ofNullable(groupMap.get((int) character)).orElse(0L);
                    if (redundantTmp < 0) {
                        return false;
                    }
                }
                return true;
            });
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
